import java.util.LinkedList;
import java.util.Queue;

public class Solution337 {
    private int[] dfs(TreeNode root){//0:抢 1:不抢
        if(root == null){
            return new int[2];
        }
        int[] res = new int[2];
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        res[0] = root.val + left[1] + right[1];
        res[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return res;
    }

    public int rob(TreeNode root) {
        int[] res = dfs(root);//0:抢 1:不抢
        return Math.max(res[0], res[1]);
    }

    public TreeNode deserialize(String data) {
        if(data.equals("")){
            return null;
        }
        String[] strNodeArr = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(strNodeArr[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int ind = 1;
        while(!q.isEmpty()){
            TreeNode tmpNode = q.poll();
            String leftStr = strNodeArr[ind++];
            String rightStr = strNodeArr[ind++];
            if(!leftStr.equals("null")){
                tmpNode.left = new TreeNode(Integer.valueOf(leftStr));
                q.add(tmpNode.left);
            }
            if(!rightStr.equals("null")){
                tmpNode.right = new TreeNode(Integer.valueOf(rightStr));
                q.add(tmpNode.right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Solution337 s = new Solution337();
        s.rob(s.deserialize("3,2,3,null,3,null,1,null,null,null,null"));
        System.out.println();
    }

}
